package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author: lynn
 * @Descript: 遍历获取所在树的分支
 * @date: 2021/6/6 23:45
 * @version: 1.0
 */
public class Q68_2_TreeNodeCommonParentNode {
    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(3);
        treeNode.left=new TreeNode(5);
        treeNode.right=new TreeNode(1);
        treeNode.left.left=new TreeNode(6);
        treeNode.left.right=new TreeNode(2);
        treeNode.right.left=new TreeNode(0);
        treeNode.right.right=new TreeNode(8);
        treeNode.left.right.left=new TreeNode(7);
        treeNode.left.right.right=new TreeNode(4);
        ArrayList<Integer> path1=findTargetTreePath(treeNode,4,5);
        System.out.println(path1);

    }

    private static ArrayList<Integer> findTargetTreePath(TreeNode root,int target1,int target2) {
        ArrayList<Integer> targetList=new ArrayList<>();
        Stack<Integer> stack = new Stack<Integer>();
        preOrder(root, stack,targetList,target1,target2);
        return targetList; //fixme 找出target节点所在的路径
    }
    private static void  preOrder(TreeNode root,Stack stack,ArrayList<Integer> targetList,int target1,int target2){
        if (root==null) return;
        stack.push(root.val);
        if (root.val==target1||root.val==target2) targetList.addAll(stack);
        preOrder(root.left, stack, targetList,target1,target2);
        preOrder(root.right, stack,  targetList,target1,target2);
        stack.pop();
    }
    private static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        TreeNode(int val){
            this.val=val;
        }
    }
}
